#include<vector>
using namespace std;
int dfs(int i, int j, vector<vector<int>>& memo)
{
    if (memo[i][j] != 0) return memo[i][j];
    if (i == 0 || j == 0) return 0;
    if (i == 1 && j == 1)
    {
        memo[i][j] = 1;
        return 1;
    }
    memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
    return memo[i][j];
}
int uniquePaths(int m, int n) {
    vector<vector<int>> memo(m + 1, vector<int>(n + 1));
    return dfs(m, n, memo);
}

int main()
{
    uniquePaths(3, 4);

	return 0;
}